package com.it.data_linkedList.ring_linked;

import com.it.data_tree.util.ColorPrintln;

import java.util.Iterator;

/**
 * @Author: CaoYouGen
 * @DateTime: 2023/05/17/10:33
 * @注释: 环形链表实现
 **/
public class RingLinkedList<T> implements Iterable<T> {
    private RingNode<T> head; // 头哨兵
    private int size;         // 长度
    
    {
        head = new RingNode<T>(null, null, null);
        head.prev = head;
        head.next = head;
    }
    
    /**
     * @param data:
     * @return void
     * @Author: CaoYouGen
     * @注释: 新增 (尾插)
     * @DateTime: 2023/5/17 10:44
     */
    public void add (T data) {
        // 上一个节点
        RingNode<T> prev = head.prev;
        // 下一个节点
        RingNode<T> next = head;
        // 新增节点
        RingNode<T> newNode = new RingNode<>(data, prev, next);
        prev.next = newNode;
        next.prev = newNode;
        size++;
    }
    
    /**
     * @param data:
     * @return void
     * @作者: Coke
     * @注释: 头插
     * @DateTime: 2023/5/17 19:15
     */
    public void addFirst (T data) {
        // 上一个节点
        RingNode<T> prev = head;
        // 下一个节点
        RingNode<T> next = head.next;
        // 插入的节点
        RingNode<T> newNode = new RingNode<>(data, prev, next);
        prev.next = newNode;
        next.prev = newNode;
        size++;
    }
    
    /**
     * @return boolean
     * @Author: CaoYouGen
     * @注释: 删除 （删除第一个）
     * @DateTime: 2023/5/17 10:45
     */
    public boolean remove () {
        // 如果没有元素则返回null
        if (head.next == head) {
            return false;
        }
        // 需要删除的元素
        RingNode<T> removed = head.next;
        // 删除元素的下一个元素
        RingNode<T> next = removed.next;
        next.prev = head;
        head.next = next;
        size--;
        return true;
    }
    
    /**
     * @param data:
     * @return boolean
     * @作者: Coke
     * @注释: 根据值删除元素
     * @DateTime: 2023/5/17 22:15
     */
    public boolean remove (T data) {
        // 找到节点
        RingNode<T> removed = getNodeByData(data);
        if (removed == null) {
            return false;
        }
        // 上一个节点
        RingNode<T> prev = removed.prev;
        // 下一个节点
        RingNode<T> next = removed.next;
        prev.next = next;
        next.prev = prev;
        return true;
    }
    
    /**
     * @return boolean
     * @作者: Coke
     * @注释: 删除最后一个
     * @DateTime: 2023/5/17 22:05
     */
    public boolean removeLast () {
        // 如果没有元素则返回null
        if (head.next == head) {
            return false;
        }
        // 需要删除的元素
        RingNode<T> removed = head.prev;
        // 删除元素的上一个元素
        RingNode<T> next = removed.prev;
        next.next = head;
        head.prev = next;
        size--;
        return true;
    }
    
    /**
     * @return int
     * @Author: CaoYouGen
     * @注释: 获取链表的长度
     * @DateTime: 2023/5/17 10:46
     */
    public int size () {
        return size;
    }
    
    /**
     * @param data:
     * @return RingNode<T>
     * @作者: Coke
     * @注释: 根据值查找对应节点
     * @DateTime: 2023/5/17 22:21
     */
    public RingNode<T> getNodeByData (T data) {
        if (head.next == head) {
            return null;
        }
        
        RingNode<T> node = head.next;
        
        while (node != head) {
            if (data.equals(node.data)) {
                return node;
            }
            node = node.next;
        }
        return null;
    }
    
    /**
     * @return void
     * @Author: CaoYouGen
     * @注释: 遍历
     * @DateTime: 2023/5/17 10:46
     */
    public void print () {
        StringBuilder builder = new StringBuilder();
        RingNode<T> node = head.next;
        boolean flag = true;
        while (node != head) {
            if (flag) {
                builder.append(node.data);
                flag = false;
            } else {
                builder.append(", ").append(node.data);
            }
            node = node.next;
        }
    }
    
    /**
     * @return Iterator<T>
     * @作者: Coke
     * @注释: 迭代器遍历
     * @DateTime: 2023/5/17 19:24
     */
    
    @Override
    public Iterator<T> iterator () {
        return new Iterator<T>() {
            // 从哨兵的下一个节点开始遍历
            RingNode<T> node = head.next;
            
            @Override
            public boolean hasNext () {
                return node != head;
            }
            
            @Override
            public T next () {
                T data = node.data;
                node = node.next;
                return data;
            }
        };
    }
    
    /**
     * @return void
     * @作者: Coke
     * @注释: 递归遍历
     * @DateTime: 2023/5/17 22:36
     */
    public void recursionPrint () {
        StringBuilder builder = new StringBuilder();
        boolean flag = true;
        recursion(head, builder, flag);
        ColorPrintln.redPrintln(builder);
    }
    
    // 递归遍历 执行逻辑
    private void recursion (RingNode<T> node, StringBuilder builder, boolean flag) {
        node = node.next;
        if (node == head) {
            return;
        }
        if (flag) {
            builder.append(node.data);
        } else {
            builder.append(", ").append(node.data);
        }
        recursion(node, builder, false);
    }
}
